//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
// 注意：
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。
// 示例 1：
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 示例 2：
//输入：s = "a", t = "a"
//输出："a"
// 示例 3:
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。 
// 提示：
// 1 <= s.length, t.length <= 10⁵
// s 和 t 由英文字母组成 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 字符串 滑动窗口 👍 1712 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

class MinimumWindowSubstring {
    public static void main(String[] args) {
        String s = "EBBANCF";
        String t = "ABC";
        Solution solution = new Solution();
        System.out.println(solution.minWindow(s, t));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    static class Solution {
        /*public String minWindow(String s, String t) {
            // 记录窗口中的词频数量
            HashMap<Character, Integer> window = new HashMap<>();
            // 记录t中的所有字符，用来查询是否存在
            HashMap<Character, Integer> map = new HashMap<>();
            // count为s中包含t字符的个数，result为最小字符串的大小, start记录最小字符串开始的位置
            int left = 0, right = 0, count = 0, result = Integer.MAX_VALUE, start = 0;
            // 将t中的字符串全部放入map中
            for (int i = 0; i < t.length(); i++) {
                map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
            }

            // 循环进行判断
            while (right < s.length()) {
                // 如果map中含有该字符，将字符的value值加一，并且将count加一
                if (map.containsKey(s.charAt(right))) {
                    char c = s.charAt(right);
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if (map.get(c).equals(window.get(c))) {
                        count++;
                    }
                }

                // 移动窗口右侧进行遍历
                right++;

                // 当计数器等于t的大小时，此时窗口需要移动
                while (count == map.size()) {
                    // 如果窗口大小小于上一个窗口的大小，更新结果
                    if (right - left < result) {
                        result = right - left;
                        start = left;
                    }

                    // 移动窗口
                    char c = s.charAt(left);
                    if (map.containsKey(c)) {
                        // 如果window中的值和map中的值数量相等是包含t的字串
                        // 如果是BBAC的情况，到第二个B才将count--
                        if (window.get(c).equals(map.get(c))) {
                            count--;
                        }
                        // 将窗口中保存值的数量减一
                        window.put(c, window.getOrDefault(c, 0) - 1);
                    }
                    left++;
                }
            }

            return result == Integer.MAX_VALUE ? "" : s.substring(start, start + result);
        }
*/
        /*public String minWindow(String s, String t) {
            Map<Character, Integer> map = new HashMap<>();
            Map<Character, Integer> window = new HashMap<>();
            int left = 0, right = 0, valid = 0, result = Integer.MAX_VALUE, start = 0;

            for (int i = 0; i < t.length(); i++) {
                map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
            }

            while (right < s.length()) {
                if (map.containsKey(s.charAt(right))) {
                    char c = s.charAt(right);
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if (map.get(c).equals(window.get(c))) {
                        valid++;
                    }
                }

                right++;

                while (valid == map.size()) {
                    if (result > right - left) {
                        result = right - left;
                        start = left;
                    }

                    char c = s.charAt(left);
                    if (map.containsKey(c)) {
                        if (map.get(c).equals(window.get(c))) {
                            valid--;
                        }

                        window.put(c, window.getOrDefault(c, 0) - 1);
                    }

                    left++;
                }
            }

            return result == Integer.MAX_VALUE ? "" : s.substring(start, start + result);
        }*/

        public String minWindow(String s, String t) {
            Map<Character, Integer> window = new HashMap<>();
            Map<Character, Integer> map = new HashMap<>();

            int l = 0, r = 0, len = Integer.MAX_VALUE, startIndex = 0, count = 0;
            for (int i = 0; i < t.length(); i++) {
                char c = t.charAt(i);
                map.put(c, map.getOrDefault(c, 0) + 1);
            }

            while (r < s.length()) {
                char c = s.charAt(r);
                if (map.containsKey(c)) {
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if (map.get(c).equals(window.get(c))) {
                        count++;
                    }
                }

                while (count == map.size()) {
                    // 更新子串
                    if (r - l < len) {
                        len = r - l + 1;
                        startIndex = l;
                    }

                    char c1 = s.charAt(l);
                    if (map.containsKey(c1)) {
                        if (map.get(c1).equals(window.get(c1))) {
                            count--;
                        }
                        window.put(c1, window.get(c1) - 1);
                    }

                    l++;
                }

                r++;
            }

            return len == Integer.MAX_VALUE ? "" : s.substring(startIndex, startIndex + len);
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
